package sort;

import java.util.Arrays;

import comment.Comment;


/**
 *create by tbj
 */
public class MergeSort{
	private static void merge(int[] a,int l,int mid,int r){
		int[] b=Arrays.copyOfRange(a, l, r+1);
		int i=l,j=mid+1;
		for(int k=l;k<=r;k++){
			if(i>mid){
				a[k]=b[j-l];
				j++;
			}else if(j>r){
				a[k]=b[i-l];
				i++;
			}
			else if(b[i-l]<b[j-l]){
				a[k]=b[i-l];
				i++;
			}else{
				a[k]=b[j-l];
				j++;
			}
		}
	}
	
	private static void _sort(int[] a,int l,int r){
		if(l >= r){	//优化  可以当元素数据量小到一定值时（r-l <= x），进行另外的排序（如插入排序）
			return;
		}
		int mid=(l+r)/2;
		_sort(a, l, mid);
		_sort(a, mid+1, r);
		//优化 不必每次都进入merge中
		if(a[mid]>a[mid+1]){
			merge(a, l, mid, r);
		}
		/*merge(a, l, mid, r);*/
	}
	
	public static void sort(int[] a){
		int n=a.length;
		_sort(a, 0, n-1);
	}
	
	public static void main(String[] args) {
		int[] a=Comment.getSortIntArr();
		MergeSort.sort(a);
		for (int i : a) {
			System.out.print(i+" ");
		}
	}
	    
}
